假设有两个决策 , 且 比 优。
#include <cstdio>
#define LL long long
#define Lint long long
const int MAXN = 1e6 , MAXK = 200;
int n , k , s[ MAXN + 5 ] , pre[ MAXK + 5 ][ MAXN + 5 ];
LL dp[ 2 ][ MAXN + 5 ];
int Que[ MAXN + 5 ] , Head , Tail;
LL fx( int i ) { return s[ i ]; }
LL fy( int k , int i ) { return dp[ ( k - 1 ) & 1 ][ i ] - 1ll * s[ i ] * s[ i ]; }
LL deltax( int i , int j ) { return fx( j ) - fx( i ) == 0 ? 1e18 : fx( j ) - fx( i ); }
LL deltay( int k , int i , int j ) { return fy( k , i ) - fy( k , j ); }
int main( ) {
scanf("%d %d",&n,&k);
for( int i = 1 ; i <= n ; i ++ )
scanf("%d",&s[ i ]) , s[ i ] += s[ i - 1 ];
for( int t = 1 ; t <= k ; t ++ ) {
Head = 1 , Tail = 0; Que[ ++ Tail ] = 0;
for( int i = 1 ; i <= n ; i ++ ) {
for( ; Head < Tail && deltay( t , Que[ Head ] , Que[ Head + 1 ] ) <= (__int128)s[ i ] * deltax( Que[ Head ] , Que[ Head + 1 ] ) ; Head ++ );
dp[ t & 1 ][ i ] = dp[ ( t - 1 ) & 1 ][ Que[ Head ] ] + 1ll * s[ Que[ Head ] ] * ( s[ i ] - s[ Que[ Head ] ] );
pre[ t ][ i ] = Que[ Head ];
for( ; Head < Tail && (__int128)deltay( t , Que[ Tail - 1 ] , Que[ Tail ] ) * deltax( Que[ Tail ] , i ) >= (__int128)deltay( t , Que[ Tail ] , i ) * deltax( Que[ Tail - 1 ] , Que[ Tail ] ) ; Tail -- );
Que[ ++ Tail ] = i;
}
}
printf("%lld\n", dp[ k & 1 ][ n ] );
for( int i = n , t = k ; t >= 1 ; t -- )
printf("%d ", i = pre[ t ][ i ] );
return 0;
}
